P=NP 問題
$ {\rm P}={\rm NP}か$ {\rm P}\ne{\rm NP}かどちらなのか証明せよという問題
なので$ {\rm P}\overset{?}{=}{\rm NP}問題とでも書くべきではある
$ {\rm P}={\rm NP}だった場合、大きく世界が変わる
計算困難性に頼った暗号が使えなくなる可能性
多分、攻撃に$ O(n^6)くらいの計算量を要するアルゴリズムに対して十分長い$ nを用意してやれば一応の対策はできるんじゃね
$ 6を選んだのは$ {\rm P}={\rm NP}だとしたら SAT の計算量が$ \Omicron(n^6)くらいになるんじゃないかなーと個人的に思っているから
万一$ {\rm P}={\rm NP}で、しかもどんな問題も$ O(n^2)とかで計算できることが証明されたりするとマズそう
指数がどこまで小さいとマズくなるんだろう
コンパイラの性能が飛躍的に向上すると期待
コンパイラ周りでは NP 完全問題にぶつかることが多い
なお、この問題は証明の難しさそのものが証明されてしまっている